This application claims priority and is entitled to the filing date of Israeli application Ser. No. 126292 filed Sep. 18, 1998, and entitled xe2x80x9cSystem And Method For Data Access,xe2x80x9d and which describes the same invention as defined herein.
The present invention relates to data access in networks. Specifically, the invention is concerned with a method, system and apparatus for increasing the speed of data accessing in communication networks.
Many known applications and protocols provide means for caching and verifying of data transmitted via a network 2 (FIG. 1, prior art). Thus, a client (receiver) 4 caches data received from network 2 in cache 6. Then, when data from a remote server (sender) 8 is requested, it first searches its local cache. If the requested data is available in the cache and is verified to be valid, the client uses it, and transmission over the network is not required. Gateway or proxy caches 10 (FIG. 2, prior art) are able to operate in a similar manner.
The most well-known techniques are as follows:
1) In response to a request from a receiver, a sender attaches to the sent data an expiration time in absolute or relative form. The receiver, and possibly proxies, cache the data together with its request until the expiration time. Then the data is retrieved from the cache. In some cases, the receiver guesses the expiration time.
The problem associated with this technique is that the data entity can be changed before the expiration time, and the receiver would use an obsolete version of the data without even knowing it. Also, when the time has expired, the data will be resent, even if it is up to date.
2) In response to a request from a receiver, the sender attaches a validator to the sent data. The validator changes at least every time the data changes; in many cases, system time is used as the validator. The receiver, and possibly proxies, cache the data together with its request. When making the next request for the same data to the same sender, the receiver includes the validator. The sender keeps track of the data and resends it only if it were changed.
The problems associated with this technique are:
a) Data is cached according to requests and senders. If the same request is directed to different servers, cached data cannot be reused.
b) Requests without concrete data cannot be cached.
c) The sender must track the cached data, which is not always possible.
None of the prior art techniques discussed above provides means for transmitting minor differences in data. Additionally, if data is retrieved through a caching proxy, there is a danger that an unauthorized user will have access to the data.
It is therefore a broad object of the present invention to provide a method, system and apparatus for increasing the speed of data access in a packet-switched network.
Another object of the present invention is to decrease data traffic throughout the network.
Still another object of the present invention is to decrease the required cache size.
A yet further object of the present invention is to maintain accessed data integrity and to improve security.
The terms xe2x80x9cdataxe2x80x9d or xe2x80x9cdata objectxe2x80x9d as used herein refer to a file or range of octets in a file, a range of frames in a video stream or RAM-based range of octets, a transport level network packet, or the like.
The term xe2x80x9cdigital digestxe2x80x9d as used herein refers to a fixed-size binary value calculated from arbitrary-size binary data in such a way that it depends only on the contents of the data and the low probability that two different data or objects have the same digital digest.
The term xe2x80x9cgatewayxe2x80x9d as used herein also includes network proxies and routers.
If a sender/computer in a network is required to send data to another receiver/computer, and the receiver/computer has data with the same digital digest as that of the data to be sent, it can be assumed with sufficient probability for most practical applications that the receiver/computer has data which is exactly the same as the data to be sent. Then, the receiver/computer can use the data immediately without its actual transfer through the network. In the present invention, this idea is used in a variety of ways.
In one embodiment of the invention, a sender/computer required to send data to a receiver/computer computer initially sends a digital digest of the data. If the receiver/computer already has data with the same digital digest, it uses this data as if it were actually transmitted from the sender/computer. Additionally, digital digests for other data objects can be sent together with the principal digest. If the receiver/computer cannot find data having the principal digest, it searches for data with one of these auxiliary digests. If such data is found, the sender/computer is required to send only the difference between the requested data object and the data object corresponding to the digest.
The expression xe2x80x9cdifference between a first data or data object and a second data or data objectxe2x80x9d as used herein means any bit sequence that enables the restoration of the first data, given the second data, the bit sequence and the method employed in calculating the difference.
The invention may be implemented in a gateway system. Such a system comprises a gateway computer connected to a packet-switched network in such a way that network packets sent between at least two other computers pass through it; a caching computer connected to the gateway computer, the caching computer having a network cache memory in its permanent storage memory, means for calculating a digital digest on the data it stores and means for comparison between a digital digest calculated on data in its network cache memory and a digital digest received from the packet-switched network by the gateway computer. When this system intercepts an indication signal other than a positive indication signal for a certain digital digest from a receiver/computer computer, if it has data with the same digest, it sends this data to the receiver/computer.
In another embodiment of the present invention, a client computer sends to a server computer a request including digital digests. A sender/computer forming a response then searches for data with the same digital digests as those received. If the digest of the data in the response equals one of the received digests, the server only sends confirmation. If the digest of another data is identical to one of the received digests, only the difference(s) between these data is sent.
In accordance with the present invention, there is therefore provided a system for data access in a packet-switched network, comprising a sender/computer including an operating unit, a first memory, a permanent storage memory and a processor and a remote receiver/computer including an operating unit, a first memory, a permanent storage memory and a processor, said sender/computer and said receiver/computer communicating through said network; said sender/computer further including means for calculating digital digests on data; said receiver/computer further including a network cache memory and means for calculating digital digests on data in said network cache memory; and said receiver/computer and/or said sender/computer including means for comparison between digital digests.
The invention also provides a system for data access in a packet-switched network, comprising a gateway computer including an operating unit, a memory and a processor connected to said packet-switched network in such a way that network packets sent between at least two other computers pass through it; a caching computer including an operating unit, a first memory, a permanent storage memory and a processor connected to said gateway computer through a fast local network; said caching computer further including a network cache memory in its permanent storage memory, means for calculating a digital digest on data stored therein and means for comparison between a digital digest calculated on data in its network cache memory and a digital digest received from said packet-switched network through said gateway computer.
In addition, the invention provides a system for data access in a packet-switched network, comprising a sender/computer including an operating unit, a first memory, a permanent storage memory and a processor and a remote receiver/computer including an operating unit, a first memory, a permanent storage memory and a processor, said sender/computer and said receiver/computer communicating through a network; said sender/computer further including means for calculating digital digests on data, and said receiver/computer further including a network cache memory, means for storing a digital digest received from said network in its permanent storage memory and means for comparison between digital digests.
The invention further provides a method performed by a sender/computer in a packet-switched network for increasing data access, said sender/computer including an operating unit, a first memory, a permanent storage memory and a processor and said sender/computer being operative to transmit data to a receiver/computer, the method comprising the steps of transmitting a digital digest of said data from said sender/computer to said receiver/computer; receiving a response signal from said receiver/computer at said sender/computer, said response signal containing a positive, partial or negative indication signal for said digital digest, and if a negative indication signal is received, transmitting said data from said sender/computer to said receiver/computer.
The invention still further provides a method for increasing data access performed by a sender/computer in a packet-switched network, said sender/computer including an operating unit, a first memory, a permanent storage memory and a processor and said sender/computer being operative to transmit principal data to a receiver/computer, said method comprising the steps of transmitting digital digests of said principal data and of one or more auxiliary data from said sender/computer to said receiver/computer; receiving a response signal at said sender/computer from said receiver/computer, said response signal containing a positive, negative or partial indication signal, and if a partial indication signal is received, said sender/computer transmitting a signal constituting the difference between said principal data and corresponding auxiliary data.
The invention yet further provides a method for increased data access performed by a receiver/computer in a packet-switched network, said receiver/computer including an operating unit, a first memory, a permanent storage memory, a processor and a network cache memory, said method comprising the steps of receiving a message containing a digital digest from said network; searching for data with the same digital digest in said network cache memory, and if data having the same digital digest as the digital digest received is not uncovered, forming a negative indication signal and transmitting it back through said network.
Still further, the invention provides a method for increased data access performed by a receiver/computer in a packet-switched network, said receiver/computer including an operating unit, a first memory, a permanent storage memory, a processor and a network cache memory, said method comprising the steps of receiving a message containing a digital digest from said network; searching for data with the same digital digest in said network cache memory, and if data having the same digital digest as the digital digest received is uncovered, forming a positive indication signal and transmitting it back through said network.
In addition, the invention provides a method for increased data access performed by a receiver/computer in a packet-switched network, said receiver/computer including an operating unit, a first memory, a permanent storage memory, a processor and a network cache memory, said method comprising the steps of receiving a message containing a principal digital digest and one or more auxiliary digital digests from said network; searching in predetermined locations in said permanent storage memory for data with a digital digest substantially identical to said principal digital digest; searching in predetermined locations in said permanent storage memory for data with a digital digest substantially identical to one of said auxiliary digital digests; and if data having the same digital digest as one of said auxiliary digital digests received is uncovered, forming a partial indication signal and transmitting it back through said network.
Yet further, the invention provides a method for increased data access performed by a computer system in a packet-switched network, said computer system including a network cache memory and being operationally interposed between a sender/computer and a receiver/computer so that data packets sent between said sender/computer and said receiver/computer are delivered through said computer system; said method comprising the steps of intercepting a message containing a digital digest transmitted from said sender/computer to said receiver/computer, and transmitting data with a digital digest substantially identical to the digital digest received from said sender/computer to said receiver/computer.
In addition, the invention provides a method for increased data access performed by a computer system in a packet-switched network, said computer system including a network cache memory and being operationally interposed between a sender/computer and a receiver/computer so that data packets sent between said sender/computer and said receiver/computer are delivered through said computer system; said method comprising the steps of intercepting a message containing a digital digest transmitted from said sender/computer to said receiver/computer; intercepting a message containing an indication signal other than a positive indication signal transmitted from said receiver/computer to said sender/computer in response to said message containing a digital digest, and transmitting data with a digital digest substantially identical to the digital digest received from said sender/computer to said receiver/computer.
Additionally, the invention provides a method for increased data access performed by a client computer in a packet-switched network, said client computer including an operating unit, a first memory and a processor, said method comprising the steps of sending a request for data from said client computer to a server, said request containing digital digests for different data; said server preparing a response to said request, searching for data with a digital digest substantially identical to one of the digital digests received in said request, and producing the difference between said response and the uncovered data.
Finally, the invention provides apparatus for increased data access in a packet-switched network, comprising a computer connected to said packet-switched network, including an operating unit, a first memory, a permanent storage memory, a processor and a network cache memory; means for calculating digital digests of data in said network cache memory; means for comparison between digital digests, and means for sending the results of comparison between a digital digest received from another computer in said network and a digital digest calculated on data in said network cache memory back to said other computer.
The invention will now be described in connection with certain preferred embodiments with reference to the following illustrative figures so that it may be more fully understood.